#include <iostream>
using std::cout;
using std::endl;

typedef int DataType;

struct Node {
  DataType data;
  Node* next;
};

class List {
 public:
  List(int max_size) : head_(nullptr), size_(0), max_size_(max_size) {}
  ~List() {
    while (head_) {
      Node* todel = head_;
      head_ = head_->next;
      delete todel;
    }
  }

  bool IsFull() const { return size_ >= max_size_; }
  int size() const { return size_; }

  // 返回头节点指针（动态更新）
  Node* Head() { return head_; }

  // 在节点后插入数据（如果是head位置，则在头部插入）
  bool InsertAfter(Node* node, const DataType& data) {
    if (size_ >= max_size_) return false;
    if (node == head_) {
      // node存的地址等于head存的地址，都指向一个节点（或nullptr）
      Node* newNode = new Node();
      newNode->data = data;
      newNode->next = head_;
      head_ = newNode;
      size_ += 1;
      return true;
    }

    if (node == nullptr) return false;

    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = node->next;  // node->next作为右值（读）
    node->next = newNode;        // node->next作为左值（写）
    size_ += 1;
    return true;
  }

  // 删除后继节点（如果只剩一个节点，则删除自己）
  bool DeleteNext(Node* node) {
    if ((node == head_) && (head_->next == nullptr)) {
      delete head_;
      head_ = nullptr;
      size_ -= 1;
      return true;
    }

    if (node == nullptr) return false;

    if (node->next) {
      Node* todel = node->next;
      node->next = node->next->next;
      delete todel;
      size_ -= 1;
      return true;
    } else {
      return false;
    }
  }

  // 删除最后一个节点（时间复杂度O(n)）
  void DeleteLast() {
    Node* p = head_;
    if (p && p->next == nullptr) {
      delete p;
      p = head_ = nullptr;
    }
    while (p && p->next) {
      if (p->next->next == nullptr) {
        Node* todel = p->next;
        p->next = p->next->next;
        delete todel;
      } else {
        p = p->next;
      }
    }
    if (size_ > 0) size_ -= 1;
  }

  // 删除指定数据的所有节点
  void DeleteData(const DataType& data) {
    Node* p = head_;
    while (p && p->next) {
      if (p->next->data == data) {
        Node* todel = p->next;
        p->next = p->next->next;
        delete todel;
        size_ -= 1;
      } else {
        p = p->next;
      }
    }

    if (head_ && head_->data == data) {
      Node* todel = head_;
      head_ = head_->next;
      delete todel;
      size_ -= 1;
    }
  }

  // 删除所有节点
  bool DeleteAll() {
    while (head_) {
      DeleteNext(head_);
    }
    size_ = 0;
  }

  // 从指定节点开始查找数据
  Node* Find(Node* node, const DataType& data) {
    if (node == nullptr) return nullptr;

    while (node) {
      if (node->data == data) {
        return node;
      }
      node = node->next;
    }
    return nullptr;
  }

  // 遍历打印链表
  void Print() {
    Node* p = head_;
    while (p) {
      cout << p->data << ' ';
      p = p->next;
    }
    cout << endl;
  }

 private:
  Node* head_;
  int size_;
  int max_size_;
};

void testList() {
  cout << "testList----\n";
  List lst(10);
  for (int i = 5; i > 0; --i) {
    lst.InsertAfter(lst.Head(), i);
  }
  lst.Print();

  Node* node2 = lst.Find(lst.Head(), 2);
  if (node2)
    cout << "node2 find: " << node2->data << endl;
  else
    cout << "node2 not find" << endl;

  Node* node3 = lst.Find(node2, 3);
  if (node3)
    cout << "node3 find: " << node3->data << endl;
  else
    cout << "node3 not find" << endl;

  Node* node1 = lst.Find(node2, 1);
  if (node1)
    cout << "node1 find: " << node1->data << endl;
  else
    cout << "node1 not find" << endl;

  lst.DeleteNext(node3);
  lst.Print();
  cout << "size:" << lst.size() << endl;

  lst.InsertAfter(lst.Head(), 3);
  lst.InsertAfter(lst.Head(), 3);
  lst.InsertAfter(lst.Head(), 3);
  lst.Print();
  lst.DeleteData(3);
  lst.DeleteData(5);
  lst.Print();
  lst.DeleteLast();
  lst.DeleteLast();
  lst.Print();

  lst.DeleteAll();
  lst.Print();
}

// 我是用的单链表（头插尾删）。删除需要找前驱节点，效率不高 时间复杂度O(n)
// 双链表更好（可以尾插头删）
int LeastRecentlyUsed(List& lst, const DataType& data) {
  lst.DeleteData(data);
  if (lst.IsFull()) {
    lst.DeleteLast();
  }
  lst.InsertAfter(lst.Head(), data);
  lst.Print();
}

void testLRU() {
  List lst(4);
  LeastRecentlyUsed(lst, 1);
  LeastRecentlyUsed(lst, 2);
  LeastRecentlyUsed(lst, 3);
  LeastRecentlyUsed(lst, 4);  // 4 3 2 1
  LeastRecentlyUsed(lst, 5);  // 5 4 3 2
  LeastRecentlyUsed(lst, 4);  // 4 5 3 2
  LeastRecentlyUsed(lst, 1);  // 1 4 5 3
}

int main() {
  // testList();
  testLRU();
  return 0;
}